
; 10 Ackermann's Function
; for y it will increase at a speed unbelievably fast!
(define (A x y)
    (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1) (A x (- y 1) )))
    )
)
; (A 1 n) = 2^n
(A 1 32)
; (A 2 n) = 2^2...^2(for n times)
(A 2 4)
; no close form for (A 3 n)?
(A 3 3)

; 11 f(n) = n if n<3 else f(n-1) + 2f(n-2) + 3f(n-3)
(define (f n)
    (define (iter count a b c)
        (if (= count n)
            a
            (iter (+ count 1) (+ a (* b 2) (* c 3) ) a b))
    )
    (if (< n 3)
        n
        (iter 2 2 1 0))
)
(f 2)
(f 3)
(f 4)
(f 5)

; 12 Compute Pascal's Triangle in recur way
(define (pascal_tri d i)
    (cond ((= d 0) 1)
        ((or (= i 0) (= i d)) 1)
        (else (+ (pascal_tri (- d 1) (- i 1)) (pascal_tri (- d 1) i)))
    )
)
(pascal_tri 4 2)

; 15 interesting way to cal large sin
; using sin x \approx x, and sin x = 3 sin(x/3) - 4 sin^3(x/3) to shrink the arg!
; suppose to eval sin a with precision \epsilon, we have O(log (a / \epsilon)) complexity
(define (sin x)
    (define (p x)
        (- (* 3 x) (* 4 (* x x x)))
    )
    (define (recur x prec)
        (if (< x prec)
            x
            (p (recur (/ x 3) prec))
        )
    )
    (recur x 0.01)
)
; also in iter way
(define (sin x)
    (define (p x)
        (- (* 3 x) (* 4 (* x x x)))
    )
    (define (iter-sin x prec)
        (define (get-count x cnt)
            (if (< x prec)
                cnt
                (get-count (/ x 3) (+ cnt 1)))
        )
        (define tcnt (get-count x 0))

        (define (get-init x tcnt)
            (if (= tcnt 0)
                x
                (get-init (/ x 3) (- tcnt 1)))
        )
        (define init (get-init x tcnt))

        (define (iter x cnt)
            (if (= cnt tcnt)
                x
                (iter (p x) (+ cnt 1))
            )
        )
        (iter init 0)
    )
    (iter-sin x 0.01)
)
(sin 3.14)

; 16 iter version of fast_exp
; the binary repr of a number explain the recursive way
; now we should design another way
; note that b^n = (b^2)^(n/2)! 
; use a state var a, and a*b^n is an invariant; a is exactly the state var!
(define (fast_exp b n)
    (define (iter a b n)
        (if (= n 0)
            a
            (if (= 0 (remainder n 2))
                (iter a (* b b) (/ n 2))            
                (iter (* a b) (* b b) (/ (- n 1) 2))
            )
        )
    )
    (iter 1 b n)
)
; to test fast_exp, uncom next line
; (fast_exp 5 1122000)


; 19 Fast-Fib
; note the state var a,b are transformed by matrix T!
; and the Fib becomes doing a matrix power problem!
; we need abstraction of data, so complete this after chap 2

; 22 & 24 runtime of prime? and fast_prime?
; primitive version of prime?
(define (prime? n)
    (define (iter cnt)
        (if (< n (* cnt cnt))
            #t
            (if (= 0 (remainder n cnt))
                #f
                (iter (+ 1 cnt))
            )
        )
    )
    (cond ((= 1 n) #f)
        ((= 2 n) #t)
        (else (iter 2))
    )
)
; (prime? 131) ; sanity check
; recording runtime prime factory
(define (timed_prime? n)
    (newline)
    (display n)
    (display "  ***  ")
    (define (start_timed_prime? n start_time)
        (if (prime? n)
            (display (- (runtime) start_time)) ; display won't return any thing
            #f
        )
    )
    (start_timed_prime? n (runtime))
)
; we can define a timed_prime_fac to test different kind of prime algo
(define (timed_prime_fac prime?)
    (lambda (n) 
        (newline)
        (display n)
        (display "  ***  ")
        (define (start_timed_prime? n start_time)
            (if (prime? n)
                (display (- (runtime) start_time)) ; display won't return any thing
                #f
            )
        )
        (start_timed_prime? n (runtime))
    )
)
(define timed_prime?  (timed_prime_fac prime?))
(timed_prime? 13111123) ; sanity check

; find 3 smallest primes larger than 1000000,10000000,100000000,100000000000,1000000000000...
(define (n_smallest_prime prime? n low_bound )
    (define timed_prime?  (timed_prime_fac prime?))
    (define (iter cnt cnum)
        (cond ((= cnt n) (display "\nfinish!") )
            ((timed_prime? cnum) (iter (+ 1 cnt) (+ 2 cnum)))
            (else (iter cnt (+ 2 cnum)))
        )
    )
    (define nl (if (= 0 (remainder low_bound 2)) (+ 1 low_bound) low_bound))
    (iter 0 nl)
)
; increase by 10, running time increase roughly by 3, which is correct
; uncom next to test
; (n_smallest_prime prime? 3 1000000000000 )

; testing fast-prime?
; first copying fermat_prime?
(define (square x)
    (* x x)
)
(define (expmod b n m)
    (if (= n 1)
        (remainder b m)
        (if (= 0 (remainder n 2))
            (remainder (square (expmod b (/ n 2) m)) m)
            (remainder (* b (square (expmod b (/ (- n 1) 2) m))) m)
        )
    )
)
(define (fermat_prime? n times)
    (define (iter cnt)
        (define guess (+ 1 (random (- n 1))))
        (if (= cnt times)
            #t
            (if (= (expmod guess n n)  guess ) 
                (iter (+ cnt 1))
                #f
            )
        )
    )
    (iter 0)
)
(define (fast_prime? n)
    (define times 
        (if (< n 1000)
            (if (= 0 (remainder n 2))
                (/ n 2)
                (/ (- n 1) 2)
            )
            1000
        )
    )
    (fermat_prime? n times)
)
(n_smallest_prime fast_prime? 3 10000000000)